package com.alexd.leetcode.contest.week101;

public class Solution3_AC {
	public int atMostNGivenDigitSet(String[] D, int N) {
        int mask = 0;
        for(String s : D){
        	mask ^= 1<<s.charAt(0)-'0';
        }
        char[] s = Integer.toString(N+1).toCharArray();
        long dp = 0;
        int e = 1;
        for(int i = 0;i < s.length;i++){
        	dp *= Integer.bitCount(mask);
        	
    		for(int j = 1;j < s[i]-'0';j++){
    			if(mask<<~j<0){
    				dp+=e;
    			}
    		}
        	if(i > 0){
        		dp += Integer.bitCount(mask);
        	}
        	if(mask<<~(s[i]-'0')>=0){
        		e = 0;
        	}
        }
        return (int)dp;
    }
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
